//
//  Problem459.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/27.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 459. 重复的子字符串 【字符对比】【字符串滑动】
 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
 示例 1:
     输入: "abab"
     输出: True
     解释: 可由子字符串 "ab" 重复两次构成。
 示例 2:
    输入: "aba"
    输出: False
 示例 3:
     输入: "abcabcabcabc"
     输出: True

 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 */
@objcMembers class Problem459: NSObject {
    func solution() {
        print(repeatedSubstringPatternDouble("abab"))
        print(repeatedSubstringPatternDouble("aba"))
        print(repeatedSubstringPatternDouble("abcabcabcabc"))
    }
    /*
     1: 创建一个空数组存储可能的重复子串 firstList:[Character]
     2: 获取第一个字符firstC，并放入上面的数组中
     3: 遍历字符串，与firstC不相等：插入数组firstList中作为重复子串
     4: 相等时，目前firstList字符就是目前可能的重复子串，（firstList个数必须能被s的个数整除），查看后面的是否都是firstList组成
        例如：abaaba： firstC = 'a'
        i=1 => 'b' 不相等，放入数组中 => [a, b]
        i=2 => 'a' 相等，判断后面是否都是有ab组成的:
            首先判断数组[a, b]的第一个字符‘a’: 那么下一个'a'的下标应该是(firstList.count * 1) = 2, 在下一个是 (firstList.count * 2) = 4 .....  确保这些下班的字符都是‘a’， 如果不是则插入firstList
            然后判断[a, b]的第二个字符‘b’:那么下一个'a'的下标应该是(firstList.count * 1 + 1) = 3, 在下一个是 (firstList.count * 2 + 1) = 5 .....  确保这些下班的字符都是‘b’, 如果不是则插入firstList
            
     */
    func repeatedSubstringPattern(_ s: String) -> Bool {
        let charts = Array(s)
        let firstC = charts[0]
        
        var firstList:[Character] = [firstC]
        for i in 1...charts.count/2 {
            if charts[i] == firstC, charts.count % i == 0 {
                var isRe = true
                for j in 0..<firstList.count {
                    var k = firstList.count + j
                    while k < charts.count {
                        if charts[k] != firstList[j] {
                            isRe = false
                            break
                        }
                        k += firstList.count
                    }
                    
                    if isRe == false {
                        break
                    }
                }
                if isRe == true {
                    return true
                }
                firstList.append(charts[i])
            } else {
                firstList.append(charts[i])
            }
        }
        
        return false
    }
    
    /*
     思路：abcabcabc是符合要求的字符串，它是由abc * 3组成的；那么把字符串最后的abc移到开头 abc abcabc  它和原来的字符应该也是相等
     但问题是：我们不知道应该从字符串尾部移动几个，所以我们每次只移动一个字符到开头，然后判断是否和原串相等
     abcabcabc
     第一次 c abcabcab 不相等 （需要和原字符对比一下）
     第二次 bc abcabca 不相等 （需要和原字符对比一下）
     第三次 abc abcabc 相等  （需要和原字符对比一下） 所以这个字符串是满足条件的
     
     abcdabc
     第一次 c abcdab 不相等  （需要和原字符对比一下）
     第一次 bc abcda 不相等  （需要和原字符对比一下）
     第三次 abc abcd 不相等  （需要和原字符对比一下）
     第四次 dabc abc 不相等  （需要和原字符对比一下）
     第五次 cdabc ab 不相等  （需要和原字符对比一下）
     第六次 bcdabc a 不相等  （需要和原字符对比一下）
     第七次 abcdabc   相等    字符回到了原来的位置，肯定，也说明肯定不满足的条件
     
     问题是这样需要移动的次数比较多，假如字符串符合条件：需要移动的次数是：最小字符的个数，不符合：需要移动str.count-1
     那么让 str=S+S,让每次移动的结果都在str中：(理解为：字符串每次向右滑动一次)
     abcabc:
     第一次：abcab(cabcab)c  第二次：abca(bcabca)bc  第三次：abc(abcabc)abc
     abcdabc
     第一次：abcdab(cabcdab)c 第二次：abcda(bcabcda)bc 第三次：abcd(abcabcd)abc 第四次：abc(dabcabcd)abc
     第五次：ab(cdabcabc)dabc 第六次：a(bcdabcabc)dabc 第七次：(abcdabc)abcdabc
     可以看出：每次移动的结果其实都在str中
     不符合条件的字符 需要移动7次（上面的例子）才会和原来的字符相等，而符合的字符串移动次数肯定 <s.count 次
     那么在 第一次～第六次字符串中没有相等的 肯定不符合
     只需把str的首和尾的字符删除： a bcdabcabcdab  c ；剩下的就是第一次到第六次的字符串，然后判断是否有 s 相等的
     */
    
    func repeatedSubstringPatternDouble(_ s: String) -> Bool {
        let str = s + s
        let startIndex = str.index(str.startIndex, offsetBy: 1)
        let endIndex = str.index(str.endIndex, offsetBy: -1)
        
        return str[startIndex..<endIndex].contains(s)
    }
}
